package cxydmmszl.chapter09.t174;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

/**
 * <li style="color: red;">Prob</li>
 * 在两个长度相等的有序数组中找到上中位数
 * <li style="color: green;">Desc</li>
 * 给定两个有序数组 arr1 和 arr2 ，已知两个数组的长度都为 N，
 * 求两个数组中所有数的上中位数。<br/>
 * 上中位数：假设递增序列长度为n，若n为奇数，则上中位数为第n/2+1个数；否则为第n个数。
 * <br/><br/>[要求]<br/>
 * 时间复杂度为 O(logN)，额外空间复杂度为 O(1)
 * <br/><br/>备注：<br/>
 * 1⩽N⩽10^5<br/>
 * 0⩽arr1[i], arr2[i]⩽10^9
 * <li style="color: green;">Input</li>
 * 第一行一个整数 N，表示数组大小。
 * 接下来一行 N 个整数，表示 arr1 内的元素。
 * 再接下来一行 N 个整数，表示 arr2 内的元素。
 * <li style="color: green;">Output</li>
 * 输出一个整数表示答案。
 * <li style="color: blue;">Link</li>CD81
 *
 * @author habitplus
 * @since 2021-10-11 15:09
 */
public class Main {
    static final StreamTokenizer st =
            new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int nextInt() {
        try {
            st.nextToken();
        } catch (Exception e) {
            e.printStackTrace();
        }
        return (int) st.nval;
    }

    public static void main(String[] args) {
        int n = nextInt();
        int[] arr1 = new int[n];
        int[] arr2 = new int[n];

        for (int i = 0; i < n; i++) {
            arr1[i] = nextInt();
        }

        for (int i = 0; i < n; i++) {
            arr2[i] = nextInt();
        }

        int ans = getUpMedian(arr1, arr2);
        System.out.println(ans);
    }

    private static int getUpMedian(int[] arr1, int[] arr2) {
        if (arr1 == null || arr2 == null
                || arr1.length == 0
                || arr1.length != arr2.length) {
            throw new RuntimeException("Argument is invalid!");
        }

        int n = arr1.length;
        int l1 = 0, r1 = n - 1;
        int l2 = 0, r2 = n - 1;

        int mid1, mid2, offset;
        while (l1 < r1) {
            mid1 = (l1 + r1) / 2;
            mid2 = (l2 + r2) / 2;

            offset = ((r1 - l1 + 1) & 1) ^ 1;
            if (arr1[mid1] > arr2[mid2]) {
                // 排除 arr1 的【右半部分】，arr2 的【左半部分】
                r1 = mid1;
                l2 = mid2 + offset;
            } else if (arr1[mid1] < arr2[mid2]) {
                // 排除 arr1 的【左半部分】，arr2 的【右半部分】
                r2 = mid2;
                l1 = mid1 + offset;
            } else {
                return arr1[mid1];
            }
        }

        return Math.min(arr1[l1], arr2[l2]);
    }
}
